1. Field of the Invention
The methodology and system relates to an improvement on the routing accuracy of GPS-based navigation systems, or “Personal Navigation Assistants” (PNAs), using a combination of user collected dynamic traffic data.
2. Description of Related Art
One of the most useful operations of a PNA is the determination of the optimal (or sub-optimal) route between two points (start and destination), based on specific criteria and constraints. The theoretical problem of the routing optimization between two nodes in a system of interconnected nodes, wherein each link (edge) between two nodes has a respective constant (static) or variable (dynamic) weight, associated with it, is known for many decades and is solved in various ways (e.g. Dijkstra, Bellman-Ford algorithms etc. for the determination of the shortest path, etc.)
The first commercially available PNAs up until today have been mainly using static data (weights), which are associated with each “road segment” (defined as a part of a road or path, of short length, and between two intersections or other two intermediate reference points), such as the mean travelling time of that road segment, which is usually determined either arbitrarily or based on the (static) speed limit of that road segment. More recent methods recommended the correlation of each road segment with time-dependent information or user-related information, so that better routing results are obtained. Such time-dependent information is e.g. the traffic data, which depends on the day and time the user passes through, and which are obtained by a PNA via an offline server and a communication channel. The information, which depends on the user, may comprise a selection of routes or user preferences based on the recorded habits and their profile.
Until now, various methods and systems have been proposed for the collection of such dynamic traffic information, such as:                traffic sensors, which provide, online/real-time or off-line, various parameters of the traffic in major roads,        mobile telephony providers, which provide information about the density of mobile phones (and thus the density of cars) in various areas, thereby providing an indication for the level of the traffic in these areas,        users of mobile telephones with GPS, which provide in real time, in central web-servers, information about the traffic conditions etc.        
All this time-variable information is collected and unified in off-line central servers, which subsequently provide their data by means of a subscription and in real time, when requested.
The majority of the available GPS-based navigation systems (for vehicles or mobile phones) use static information, which is recorded in maps, in order to execute navigation calculation and to define specific routes from a given start to a given destination (or via intermediate destinations). During the last 5 years, there have been many proposals in the literature about the improvement of the routing capabilities of these systems, by inputting non-static (or time-variable) data, which is collected mainly from external sources and stations (sensors, web-servers etc.), as well as through various communication channels, such as GSM/GPRS/WiFi/WiMAX/etc. connections.
Furthermore, the method of data collection from mobile PNAs and their free distribution to PNA users have been used for the last 3 years by the OpenStreetMap Foundation (http://www.openstreetmap.org). However, this data is of general type (i.e. not directly exploitable by the available PNAs) and the respective systems do not process nor distribute road-segment related information for the optimization of the routing, but simply compose a common global map without traffic data about the road network.